package com.lfs.dp;

/*
    斐波那契数列

    动态规划五步曲:
    1. 确定dp数组（dp table）以及下标的含义
    2. 确定递推公式
    3. dp数组如何初始化
    4. 确定遍历顺序
    5. 举例推导dp数组
 */
public class Fib509 {
    /*
        1 1 2 3 5 8     后面的每一项数字都是前面两项数字的和。
        1、dp[i]的定义为：第i个数的斐波那契数值是dp[i]
        2、状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]; 题目给了
        3、dp数组如何初始化  F(0) = 0，F(1) = 1      题目给了
        4、确定遍历顺序 顺序遍历 从前向后
        5、debug

        先想递推公式,因为第一步初始化需要再递推公式的基础上
     */

    public int fib(int n) {
        /*
            假设没有 if (n < 2) return n; 的限制 如果传过来n=0;那我们只会创建一个dp长度为1的数组,这时就有问题了,我们初始化必要的dp[1] = 1 长度其实为2,索引就越界了
            为了满足我们初始化的要求可以:(本题采用第二种方式)
                第一种方式:  int[] dp = new int[n + 2]; 创建新数组时多给一个长度,这样n=0时, dp[1] = 1也不会越界
                第二种方式:  if (n < 1) return n; 直接加上限制,只有 n>=1时才走我们的逻辑进行初始化,否则直接返回n本身(直接返回n本身其实和初始化进行的操作一模一样)
         */
        if (n < 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        /*
            i从2开始
            0 1 2
            因为i = 2 时,求的是前面两个数的和,所以我们从2开始 求索引为 0 1的和
            注意: index，我们用的是i, n只管遍历的次数,索引其实是i
         */
        for (int index = 2; index <= n; index++) {//dp[0] = 0 dp[1] = 1 dp[n] = n 我们求的就是dp[n],所以可以等于n
            dp[index] = dp[index - 1] + dp[index - 2];// 只有index能够等于n时,才有 dp[n] = ...
        }
        return dp[n];
    }

    // 状态压缩版本
    /*

        dp[0] = 0;
        dp[1] = sum;
        目的是求c
        注意前一个数
       0 1 2 3 4 5 6 :索引 i<n(6)假设传过来一个6 ,不会遍历到6,只会用到6之前的数,所以i<n
       0 1 1 2 3 5 8  :c
       a b c
         a b c
       先求和得出c,然后给b c 赋值 用于下次c的计算
     */
    public int fib2(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 1; i < n; i++) {
            c = a + b;//先求和
            a = b;
            b = c;
        }
        return c;
    }
}
